Leetcode刷题记录(Java)

发表于 | 更新于: | 分类于
Problem 754 Reach a Number/Problem 784 Letter Case Permutation

Problem 754 Reach a Number
unI2GR.png
从原点出发,需要经过多少步可以到达指定值,步数大小可正可负且每次步数大小递增1,也就是第一次可以走1步(无论左右),第二次走2步(无论左右)…

主要思路:
这个题目考的是数学思想,我本来开始只想着一直向目标值靠近,但是超过了就退回当前值的做法,这种做法会造成靠近目标值时步数的极具增加,因为每次步数只能增加1了.比如为了接近18,我先让1+2+3+4+5+6,当加6时已经超过18,所以我变成1+2+3+4+5-6之后+7-8+9的形式.后来看到别人的正确解法明白了这个题目的关键在于理解距离,同样采取一直向目标值接近的办法,只是在超过目标值之后比较当前累加值和目标值的差,如果差值为偶数的话就能返回累加步数-1了,比如要达到30,我们首先1+2+3+4+5+6+7+8=36>30,36-30=6为偶数,而这个6其实可以通过将3转为-3即可.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int reachNumber(int target) {
        int newTarget = Math.abs(target);
        int step = 0, sum = 0;
        while (sum < newTarget || (sum - newTarget) % 2 == 1) {
            sum += step;
            step++;
        }
        return step - 1;
    }
}

Problem 784 Letter Case Permutation
unq1rq.png
小写字母的全排列问题

主要思路:
当检测到字母的时候就进入递归,下标增加,当下标达到字符串长度时就加入list.

代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<String> letterCasePermutation(String S) {
        List<String> strings = new ArrayList<>();
        letterCasePermutation(S, S.toCharArray(), strings, 0);
        return strings;
    }

    private void letterCasePermutation(String s, char[] chars, List<String> strings, int position) {
        if (position == s.length()) {
            strings.add(new String(chars));
            return;
        }
        char ch = s.charAt(position);
        if (Character.isLetter(ch)) {
            chars[position] = Character.toLowerCase(ch);
            letterCasePermutation(s, chars, strings, position+1);
            chars[position] = Character.toUpperCase(ch);
        }
        letterCasePermutation(s, chars, strings, position+1);
    }
}